/*
	从有序顺序表中删除所有重复的元素,如果是无序表呢？
*/

#include<stdio.h>
#include<malloc.h>
#include"..\Sequence_List\zyf_SqList.h"

void del_all_same1(SqList *L)
{
	int i,j,s;
	i = 0;
	j = 1;
	s = 0;

	if (L -> length == 0)
		printf("该表是空表\n");
	for (;j <= L -> length; i++,j++)
	{
		if (L -> elem_array[i] == L -> elem_array[j])
			s++;
		else
			L -> elem_array[i-s] = L -> elem_array[i];
	}

	L -> length = L -> length - s;
}

void del_all_same2(SqList *L)//书中答案的方法,空间复杂度更低
{
	if (L -> length == 0)
		printf("该表是空表\n");
	int i,j;
	for (i = 0,j = 1;j <L -> length;j++)
	{
		if (L -> elem_array[i] != L -> elem_array[j])
			L -> elem_array[++i] = L -> elem_array[j];//关键步骤，提前自增i，后面的值赋值给i
	}

	L ->length = i+1;
}

int main(void)
{
	struct sqlist L;

	printf("初始化状态为%d\n",Init_SqList(&L));

	printf("插入状态为%d\n",Insert_SqList(&L, 1, 1));
	printf("插入状态为%d\n",Insert_SqList(&L, 2, 2));
	printf("插入状态为%d\n",Insert_SqList(&L, 3, 2));
	printf("插入状态为%d\n",Insert_SqList(&L, 4, 2));
	printf("插入状态为%d\n",Insert_SqList(&L, 5, 2));
	printf("插入状态为%d\n",Insert_SqList(&L, 6, 3));
	printf("插入状态为%d\n",Insert_SqList(&L, 7, 3));
	printf("插入状态为%d\n",Insert_SqList(&L, 8, 3));
	printf("插入状态为%d\n",Insert_SqList(&L, 9, 4));
	printf("插入状态为%d\n",Insert_SqList(&L,10, 4));
	printf("插入状态为%d\n",Insert_SqList(&L,11, 5));

	putchar('\n');
	for (int i = 0 ; i < L.length ; i++)
	{
		printf("第%d个值为:%d\n",i+1,L.elem_array[i]);
	}

	//del_all_same1(&L);
	del_all_same2(&L);
	puts("\n------------------------------------------");

	for (int i = 0 ; i < L.length ; i++)
	{
		printf("第%d个值为:%d\n",i+1,L.elem_array[i]);
	}


}